package com.base.dp;

public class LongestPalindrome {
    public static void main(String[] args) {
        LongestPalindrome lp = new LongestPalindrome();
        System.out.println();
        lp.foreach("abbahjjjjh");
    }

    public String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";
        int n = s.length();
        //dp[i][j] 表示字符串从索引 i 到 j 的子串是否是回文串。
        boolean[][] dp = new boolean[n][n];
        //单个字符都是回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = true;
        }
        /**
         * 状态转移方程如下：
         *
         * 当 s[i] == s[j]（即子串的两端字符相同）时，如果子串的长度为1或2（即 j - i <= 1），那么 dp[i][j] = true，因为单个字符或者是两个相同字符的子串都是回文串。
         * 如果 s[i] == s[j] 且 dp[i + 1][j - 1] 为 true（即内部子串也是回文串），那么 dp[i][j] = true。
         * 如果上述条件都不满足，则 dp[i][j] = false。
         * 初始化时，所有 dp[i][i] 应为 true，因为单个字符都是回文串。
         */
        int start = 0, end = 0;
        //子串长度从2开始,表示啥呢，意思是先排查一遍长度为2的子串是否存在，然后是3、以此类推
        for (int len = 2; len <= n; len++) { // n == 6
            //i从起始位置开始，到
            for (int i = 0; i <= n - len; i++) {  // i == [0,4]
                int j = len + i - 1; // j = [1,5]
                if (s.charAt(i) == s.charAt(j)) {
                    if (len == 2) {
                        dp[i][j] = true;
                    } else {
                        //如果内部子串也是回文串
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    dp[i][j] = false;
                }

                // 更新最长回文子串的起始和结束位置  len > end - start  如果当前长度已经大于上次的长度，那么就更新，用于计算最长的子串
                if (dp[i][j] && len > end - start) {
                    start = i;
                    end = j;
                }
            }
        }
        return s.substring(start, end + 1);
    }


    private void foreach(String s){
        int n = s.length();
        //长度从小变大，先填充里面的，在写外面的
        for (int len = 2; len <= n; len++) { // n == 6
            //i从起始位置开始，到
            System.out.println("=============len ============== "+len);
            for (int i = 0; i <= n - len; i++) {  // i == [0,4]
                int j = len + i - 1;
                System.out.println("i="+i+" i+1="+(i+1)+" j="+j+"   j-1="+(j-1));
            }
        }
    }
}
